/**
 * 
 */
package uk.ac.manchester.cs.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * TODO Inherit it from Forest
 * 
 * <p>Title: Tree</p>
 * 
 * <p>Description: 
 * </p>
 * 
 * <p>Copyright: Copyright (c) 2007, 2008</p>
 * 
 * <p>Company: Clark & Parsia, LLC. <http://www.clarkparsia.com></p>
 * 
 * @author pavel
 */
public class Tree<T> {
	 
    private Node<T> m_root;
     
    public Tree(T root) {
    	
    	init(root);
    }    
 
    public Node<T> getRoot() {
    	
        return this.m_root;
    }
 

    public void setRoot(Node<T> root) {
    	
        this.m_root = root;
        root.setParent(null);
    }
     
    public List<Node<T>> nodeList(Node<T> start) {
    	
        List<Node<T>> list = new ArrayList<Node<T>>();
 
        walk(start, list, false);
        
        return list;
    }    
    
    public List<T> dataList(Node<T> start) {
    	
    	List<T> list = new ArrayList<T>();
    	
    	dataWalk(start, list, false);
    	
    	return list;
    }
    
    
    public List<Node<T>> getLeafs(Node<T> start) {
    	
        List<Node<T>> list = new ArrayList<Node<T>>();
        
        walk(start, list, true);
        
        return list;
    }
    
    public List<T> getLeafObjects(Node<T> start) {
    	
    	List<T> list = new ArrayList<T>();
    	
    	dataWalk(start, list, true);
    	
    	return list;
    }    
    
    public String toString() {

    	StringBuffer sb = new StringBuffer();
    	
    	m_root.output(sb, 0);
    	
    	return sb.toString();
    }
    
    /**
     * Walks the Tree in pre-order style. This is a recursive method, and is
     * called from the toList() method with the root element as the first
     * argument. It appends to the second argument, which is passed by reference
     * as it recurses down the tree.
     * @param element the starting element.
     * @param list the output of the walk.
     */
    private void walk(Node<T> element, List<Node<T>> list, boolean leafsOnly) {
    	
    	if ((!leafsOnly || element.isLeaf()) && !element.isDead()) {
    		
    		list.add(element);
    	}
        
        for (Node<T> data : element.getChildren()) {
        	
        	if (!data.isDead()) {
        		walk(data, list, leafsOnly);
        	}

        }
    }

    private void dataWalk(Node<T> element, List<T> list, boolean leafsOnly) {
    	
    	if ((!leafsOnly || element.isLeaf()) && !element.isDead()) {

    		list.add(element.getObject());
    	}
        
        for (Node<T> data : element.getChildren()) {

        	if (!data.isDead()) {
        		dataWalk(data, list, leafsOnly);
        	}
        }
    }
    
    
    public Tree<T> cloneTree() {
    	
    	Tree<T> tree = newTree();
    	
    	if (null != m_root) {
    		//clone will recursively clone nodes
    		Node<T> root = m_root.cloneNode( null );
    		
    		tree.setRoot( root );
    	}
    	
    	return tree;
    }
    
    protected Tree<T> newTree() {
    	
    	return new Tree<T>(null);
    }
    
	protected void init(T object) {
		
		m_root = new Node<T>(null, object);
	}
    
}